package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 数组中重复的数据_442 {

    /*
    * 其实就是一个 完全抽屉问题
    * 1 <= a[i] <= n
    *  所以 如果没有重复的元素的话 ----> 那么每个位置都会放上相应的数字
    * 如果 有重复的元素的话，说明 有的位置会被占，
    * */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int length = nums.length;
       //  将数组中的元素放到自己该有的位置
        int j =0;
        while( j <length){
            if( nums[j] == j+1){
                continue;
            }
            int temp = nums[j];
            if(nums[temp-1] == temp){
                j ++;
            }else{
                nums[j] = nums[temp-1];
                nums[temp-1] = temp;
            }
        }
        for(int i=0; i <length ; i++){
            if( nums[i] != i+1){
                result.add(nums[i]);
            }
        }
        return result;
    }
}
